#include <iostream>
#include <vector>
using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x)
		:val(x)
		,left(nullptr)
		,right(nullptr)
	{}
	TreeNode(int x, TreeNode* r, TreeNode* l)
		:val(x)
		,left(l)
		,right(r)
	{}
};
class Solution 
{
public:
	bool flag = false;
	void dfs(TreeNode* root, vector<int>& path, int traget)
	{
		if (!root || flag)
			return;
		path.emplace_back(root->val);
		if (root->val == traget)
		{
			flag = true;
			return;
		}
		
		dfs(root->left, path, traget);
		dfs(root->right, path, traget);
		if (flag)
			return;
		path.pop_back();
	}
	int lowestCommonAncestor(TreeNode* root, int o1, int o2) 
	{
		vector<int> path1, path2;

		dfs(root, path1, o1);
		flag = false;
		dfs(root, path2, o2);
		int res;
		for (int i = 0; i < path1.size() && i < path2.size(); i++)
		{
			if (path1[i] == path2[i])
			{
				res = path1[i];
			}
			else
				break;
		}
		return res;
	}
};
int main()
{
	TreeNode* H = new TreeNode(4);
	TreeNode* G = new TreeNode(7);
	TreeNode* F = new TreeNode(8);
	TreeNode* E = new TreeNode(0);
	TreeNode* D = new TreeNode(2, G, H);
	TreeNode* C = new TreeNode(6);
	TreeNode* B = new TreeNode(1, E, F);
	TreeNode* A = new TreeNode(5, C, D);

	TreeNode* root = new TreeNode(3, A, B);


	Solution xz;
	int n = xz.lowestCommonAncestor(root,5, 1);
	cout << n << endl;


	return 0;
}